package queue.priorityQueue;

import queue.Queue;

/**
 * 基于<b>大顶堆</b>实现
 *
 * @author yyz
 * @create 2024-01-09 19:29
 */
@SuppressWarnings("all")
public class PriorityQueue3<E extends Priority> implements Queue<E> {
    Priority[] array;
    int capacity;
    int size = 0;

    public PriorityQueue3(int capacity) {
        this.capacity = capacity;
        array = new Priority[capacity];
    }

    /*
        如果从索引 0 开始存储节点数据
            节点之的父节点为 floor((i-1)/2)，当i>0时
            节点i的左子节点为2i+1，右子节点为 2i+2，当然它们得 < size。
        如果从索引1开始存储节点数据
            节点i的父节点为 floor(i/2)，当i>1时。
            节点i的左子节点为 2i，右子节点为 2i+1，同样得< size
     */
    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        int chalid = size++;
        int parent = (chalid - 1) / 2;
        while (chalid > 0 && value.priority() > array[parent].priority()) {
            array[chalid] = array[parent];
            chalid = parent;
            parent = (chalid - 1) / 2;
        }
        array[chalid] = value;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        Priority val = array[0];
        // 交换0索引和size-1索引值
        swap(0, size - 1);
        array[--size] = null;

        // 下潜
        down(0);
        return (E) val;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[0];
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    private void swap(int i, int j) {
        Priority t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    private void down(int index) {
        int left = 2 * index + 1;
        int right = left + 1;
        int max = index;
        if (left < size && array[max].priority() < array[left].priority()) {
            max = left;
        }
        if (right < size && array[max].priority() < array[right].priority()) {
            max = right;
        }
        if (max != index) {
            swap(index, max);
            down(max);
        }
    }
}
